<h1>The Deadpixi Garbage Collector</h1>

<h2>Introduction</h2>

<p>The Deadpixi Garbage Collector (dpgc) is a simple tri-color garbage collection
library written in pure C. It is an explicitly-managed collector, meaning that
it is up to the programmer to add objects to the collector and to notify the
collector when one object adds a reference to another object. These
limitations allow the code to be extremely small and portable.</p>

<p>The collector was designed to be useful as a garbage collector for the
implementation of a higher-level language compiler/interpreter, or to ease the
implementation of persistent data structures (like ropes and zippers) in C.</p>

<h2>Using DPGC in Your Project</h2>

<p>Simply include <code>collector.h</code> wherever necessary and link with <code>collector.c</code>.
Compiled without debugging, the code is around 5KB.</p>

<p>Note that by default, DPGC uses a lot of assertions to verify the state of its
code at runtime. While these are useful debugging aids, they slow down 
execution considerably. When compiling DPGC for production deployment,
consider defining the C-standard <code>NDEBUG</code> preprocessor symbol to disable 
these assertions.</p>

<h2>Definitions and Theory of Operation</h2>

<p>dpgc uses the well-known tri-color collection algorithm, which allows 
incremental collection of garbage. This greatly reduces (but does not 
necessarily eliminate) long pauses during execution while the collector runs.</p>

<p>dpgc is a <strong>garbage collector</strong>, which means that it tracks <strong>objects</strong> 
in memory and automatically frees their storage when they are no longer needed.
It does this by determining if a given object is <strong>reachable</strong>.</p>

<p>Reachability is determined by <strong>references</strong> between and among objects. An
object can hold a reference to another object, which may itself hold references
to other objects, and so on.</p>

<p>A special set of objects, the <strong>roots</strong>, are used by the collector to determine
reachability - if an object is reached by following a set of references from
any root, that object is reachable and its storage is not reclaimed. A good
example of a set of roots would be the registers of a virtual machine along 
with object references in all the activation frames on the stack.</p>

<p>dpgc is an <strong>incremental</strong> collector. That means that it tries to avoid long
pauses during execution to run, and instead collects garbage in pieces during
execution. This generally takes more time overall, but this time is amortized
over the runtime of the program, greatly increasing responsiveness on average.
(Note that dpgc is <strong>not a deterministic collector</strong> and long pauses are 
certainly possible, though hopefully rare.)</p>

<p>To use dpgc, a programmer creates objects using whatever memory allocation
method best suits the task at hand (e.g. <em>malloc(3)</em>) and registers them with
the collector. After an object is registered, the programmer must notify the
collector if the object is <strong>mutated</strong> in such a way that it obtains a
reference to another object.</p>

<p>A collector may be <strong>paused</strong> or <strong>unpaused</strong>. Before an object (including a 
root) is added or mutated, the collector must be paused. When the collector is
paused, no management of objects occurs. When the collector is unpaused,
management of objects resumes. </p>

<h2>Adding, Touching and Disposing of Objects</h2>

<p>All objects managed by the collector must be structures and the first member
of these structures must be a <code>Collectee</code> structure. The <code>Collectee</code> structure
is an opaque structure used to hold tracking information for the collector.</p>

<p>The programmer must provide two functions to the collector, referred to as the
<em>touch</em> and <em>dispose</em> functions.</p>

<p>The <em>touch</em> function is called by the collector with some managed object. This
function must call the <em>touchobj</em> function on every object that is directly
reachable (i.e. exactly one reference away) from the passed-in object.</p>

<p>The <em>dispose</em> function is called by the collector with some managed object when
that object ceases to be reachable and its storage can therefore be reclaimed.
How (or even if) the object's storage is actually reclaimed is up to the 
implementation of the <em>dispose</em> function, but in any case, after <em>dispose</em>
is called on an object, it is no longer managed by the collector.</p>

<p>By asking the programmer to write custom <em>touch</em> and <em>dispose</em> functions, 
dpgc allows a much greater level of flexibility in implementation. For example,
a higher-level language interpreter could have a touch function that knows 
about the primitive data structures of the implemented language and therefore
knows what objects could be referenced from each.</p>

<h2>Basic Workflow</h2>

<p>To use dpgc, the programmer must follow something like the following simplified
workflow:</p>

<ol>
<li>Create a collector structure.</li>
<li>Write <em>touch</em> and <em>dispose</em> functions and register them with the collector.</li>
<li>Create some set of roots and register them with the collector.</li>
<li>Create objects as needed and register them with the collector.</li>
<li>Notify the collector whenever one object obtains a reference to another.</li>
</ol>

<h2>The Tag Field</h2>

<p>The standard <code>Collectee</code> structure contains a <code>tag</code> member. This is a normal
C integer. It is not used by the collector, and is free to use by the 
programmer-provided <code>touch</code> and <code>dispose</code> functions to determine the type of
the object passed in.</p>

<h2>Function Reference</h2>

<h3>Creating a Collector</h3>

<pre><code>Collector *
makecollector(int (*touch)(Collector *, Collectee *), 
            void (*dispose)(Collector *, Collectee *));
</code></pre>

<p>Creates and returns a new <code>Collector</code> object. Returns <code>NULL</code> on failure. Note
that the newly-created collector is in the <em>paused</em> state and therefore
<strong>at least one call to <code>unpausegc</code> must be made to have the collector start
running</strong>.</p>

<p>The two passed-in function pointers must point to the programmer-provided
<code>touch</code> and <code>dispose</code> functions (see below).</p>

<h3>Programmer-Provided Functions</h3>

<pre><code>int  (*touch)(Collector *, Collectee *);

void (*dispose)(Collector *, Collectee *);
</code></pre>

<p>The programmer must provide two functions: <code>touch</code> and <code>dispose</code>. </p>

<p>The <code>touch</code> function is called with various managed objects and must call the
<code>touchobj</code> function on every managed object for which the passed-in object
holds a direct reference. The <code>touch</code> function must return nonzero when this
requirement has been completed. If the <code>touch</code> function returns zero, the
collector interprets this as meaning that the passed-in object will need to be
passed in again at a later time to complete the work. This allows objects to
be marked incrementally, but it is up to the implementation of the <code>touch</code>
function to maintain state between invocations on the same object. </p>

<p>The <code>dispose</code> function is called with a managed object when that object is no
longer reachable from any root and its storage can therefore be reclaimed. The
<code>dispose</code> function need not actually reclaim any storage (that is up to the
programmer to determine), but in any case, once <code>dispose</code> is called on an 
object it ceases to be managed by the collector.</p>

<h3>Adding an Object or Root</h3>

<pre><code>void
addobj(Collector *, Collectee *, Collectee *);

void
addroot(Collector *, Collectee *);
</code></pre>

<p>Adds an object or root to the collector. While it is possible to add a root at
any time, <strong>at least one root must be added to the collector before it begins
running</strong>. Additionally, <strong>the collector must be in the paused state before
an object or root may be added</strong>.</p>

<p>While an object may be added without another managed object holding a reference
to it, this would allow the newly-added object to be disposed of immediately
(since it is not reachable from any other managed object). Therefore, commonly
an object is added and a reference is immediately added to it while the 
collector is still paused. The third argument to <code>addobj</code>, if it is not <code>NULL</code>
is treated as an object holding a reference to the newly-added object.</p>

<h3>Removing a Root</h3>

<pre><code>void
removeroot(Collector *, Collectee *);
</code></pre>

<p>Removes a root, transforming it into a regular object subject to collection.
This function is useful in the creation of persistent functional data 
structures in C, where a new object may become the root at any time. <strong>The
collector must be in the paused state before a root may be removed and there
must be at least one root remaining after removal.</strong></p>

<h3>Tracing Objects</h3>

<pre><code>void
touchobj(Collector *, Collectee *);
</code></pre>

<p>The <code>touchobj</code> function must be called by the programmer-provided <code>touch</code>
function on each managed object for which the passed-in object holds a 
reference.</p>

<h3>Mutating Objects</h3>

<pre><code>void
addref(Collector *, Collectee *, Collectee *);
</code></pre>

<p>The <code>addref</code> function lets the collector know that some managed object now 
holds a reference to another object (the first object is the referer object,
the second is the referee). <strong>The collector must be in the paused state before
an object may be mutated.</strong></p>

<h3>Stepping the Collector</h3>

<pre><code>void
stepgc(Collector *, unsigned int);
</code></pre>

<p>The collector can be caused to run for a specified number of steps using the
<code>stepgc</code> function. However, this is generally not needed as the collector will
run for <code>GC_STEP_FACTOR</code> steps every time the <code>addobj</code> function is called.</p>

<p>A step in this context generally corresponds to the tracing of one managed
object's held references. If there are no remaining objects that need to be
traced, all disposable objects have their storage reclaimed.</p>

<p>By default <code>GC_STEP_FACTOR</code> is 3, meaning that collection runs about three 
times the speed of allocation (though of course, objects can be arbitrarily
long-lived). If <code>GC_STEP_FACTOR</code> is defined to be 0, all collection stepping
must be done via the <code>stepgc</code> function.</p>

<h3>Pausing and Unpausing the Collector</h3>

<pre><code>void
pausegc(Collector *);

void
unpausegc(Collector *);
</code></pre>

<p>The collector must be in the paused state during various operations. While in
the paused state, no management of objects occurs.</p>

<p>The collector may be placed in the paused state by calling the <code>pausegc</code>
function and removed from the paused state by calling the <code>unpausegc</code> function.
These calls may be nested, but must be balanced.</p>

<h3>Allocating Storage</h3>

<pre><code>void *
gcalloc(Collector *, size_t);
</code></pre>

<p>The <code>gcalloc</code> function will allocate the specified number of bytes using the
standard <code>calloc(3)</code> function. If the allocation fails, the collector is 
stepped until either the allocation succeeds or the collector has run a full
cycle and reclaimed the storage of all disposable objects (implying that 
free storage has been exhausted).</p>

<h2>A Simple Example</h2>

<p>Here is a simple example of a garbage-collected linked list:</p>

<pre><code>#include &lt;stdio.h&gt;
#include &lt;stdlib.h&gt;
#include &lt;collector.h&gt;

typedef struct Node Node;
struct Node{
    Collectee collectee; /* All managed objects must begin with this. */
    Node *next;
    int i;
};

int
touch(Collector *collector, Collectee *collectee)
{
    Node *node;

    node = (Node *)collectee;

    printf("tracing references held by %p\n", collectee);

    if(node-&gt;next != NULL)
        touchobj(collector, (Collectee *)(node-&gt;next));

    return 1;
}

void
dispose(Collector *collector, Collectee *collectee)
{
    printf("disposing of %p\n", collectee);
    free(collectee);
}

int
main(void)
{
    Collector *col;
    Node      *head;
    Node      *node;
    Node      *prev;
    int       i;

    col = makecollector(touch, dispose);
    if(col != NULL){
        head = calloc(1, sizeof(Node));
        if(head != NULL){
            addroot(col, (Collectee *)head);

            prev = head;
            for(i = 0; i &lt; 9999; i++){
                node = gcalloc(col, sizeof(Node));
                if(node != NULL){
                    node-&gt;i = i;

                    /* Create 4999 reachable objects, and make the other
                     * 5000 objects unreachable so that they can be
                     * collected. */
                    if(i &lt; 5000){
                        prev-&gt;next = node;  
                        addobj(col, (Collectee *)node, (Collectee *)prev);
                    } else
                        addobj(col, (Collectee *)node, NULL);

                    prev = node;
                } else{
                    fprintf(stderr, "unable to allocate list node\n");
                    exit(EXIT_FAILURE);
                }
            }
        } else{
            fprintf(stderr, "unable to allocate list root\n");
            exit(EXIT_FAILURE);
        }
    } else{
        fprintf(stderr, "unable to allocate collector\n");
        exit(EXIT_FAILURE);
    }

    /* Normally, one would start the collector long before now, but
     * this provides an example of a large number of unreachable objects
     * simply. */
    unpausegc(col);

    return EXIT_SUCCESS;
}
</code></pre>

<h2>References</h2>

<ul>
<li><a href="http://code.google.com/p/dpgc/">DPGC Homepage</a></li>
<li><a href="http://www.deadpixi.com/">Deadpixi.COM</a></li>
<li><a href="http://www.gnu.org/licenses/lgpl-3.0.txt">GNU Lesser General Public License</a></li>
</ul>
